#include <vector>

using namespace std;

// 戳印序列
// 你想最终得到"abcbc"，认为初始序列为"?????"。印章是"abc"
// 那么可以先用印章盖出"??abc"的状态，
// 然后用印章最左字符和序列的0位置对齐，就盖出了"abcbc"
// 这个过程中，"??abc"中的a字符，被印章中的c字符覆盖了
// 每次盖章的时候，印章必须完全盖在序列内
// 给定一个字符串target是最终的目标，长度为n，认为初始序列为n个'?'
// 给定一个印章字符串stamp，目标是最终盖出target
// 但是印章的使用次数必须在10*n次以内
// 返回一个数组，该数组由每个回合中被印下的最左边字母的索引组成
// 上面的例子返回[2,0]，表示印章最左字符依次和序列2位置、序列0位置对齐盖下去，就得到了target
// 如果不能在10*n次内印出序列，就返回一个空数组
// 测试链接 : https://leetcode.cn/problems/stamping-the-sequence/

// 自己实现的队列
class Solution 
{
public:
    vector<int> movesToStamp(string stamp, string target) 
    {
        int m = stamp.size(), n = target.size();
        vector<int> indegree(n - m + 1, m);
        vector<vector<int>> g(n);
        int l = 0, r = 0, q[n - m + 1];
        memset(q, 0, sizeof(q));
        for(int i = 0; i <= n - m; ++i)
        {
            // i 开头的 m 个字符
            for(int j = 0; j < m; ++j)
            {
                if(target[i + j] == stamp[j])
                {
                    if(--indegree[i] == 0) q[r++] = i;
                }
                else
                {
                    // from：错误的位置，to：i 开头的下标
                    g[i + j].push_back(i);
                }
            }
        }

        // 标记被取消错误的位置
        vector<bool> visited(n);
        vector<int> ret(n - m + 1);
        int cnt = 0;
        while(l < r)
        {
            int x = q[l++];
            ret[cnt++] = x;
            // x : 开头位置，取消 x, x + 1, x + 2 ... x + m - 1 等位置的错误
            for(int i = 0; i < m; ++i)
            {
                if(!visited[x + i])
                {
                    visited[x + i] = true; // 取消错误
                    for(int y : g[x + i])
                    {
                        if(--indegree[y] == 0)
                        {
                            q[r++] = y;
                        }
                    }
                }
            }
        }

        if(cnt != n - m + 1) return {};
        reverse(ret.begin(), ret.end());
        return ret;
    }
};


// 使用标准库的队列
class Solution 
{
public:
    vector<int> movesToStamp(string stamp, string target) 
    {
        int m = stamp.size(), n = target.size();
        vector<int> indegree(n - m + 1, m);
        vector<vector<int>> g(n);
        queue<int> q;
        for(int i = 0; i <= n - m; ++i)
        {
            // i 开头的 m 个字符
            for(int j = 0; j < m; ++j)
            {
                if(target[i + j] == stamp[j])
                {
                    if(--indegree[i] == 0) q.push(i);
                }
                else
                {
                    // from：错误的位置，to：i 开头的下标
                    g[i + j].push_back(i);
                }
            }
        }

        // 标记被取消错误的位置
        vector<bool> visited(n);
        vector<int> ret(n - m + 1);
        int cnt = 0;
        while(!q.empty())
        {
            int x = q.front();
            q.pop();
            ret[cnt++] = x;
            // x : 开头位置，取消 x, x + 1, x + 2 ... x + m - 1 等位置的错误
            for(int i = 0; i < m; ++i)
            {
                if(!visited[x + i])
                {
                    visited[x + i] = true; // 取消错误
                    for(int y : g[x + i])
                    {
                        if(--indegree[y] == 0)
                        {
                            q.push(y);
                        }
                    }
                }
            }
        }

        if(cnt != n - m + 1) return {};
        reverse(ret.begin(), ret.end());
        return ret;
    }
};